有限背包 - 單調隊列優化

我們先列出轉移式

可以發現，對於 dp(i, j)，他能轉移的點可能就是 j - 2w, j - w, j，對於 dp(i, j - w)，他能轉移的點可能就是 j - 3w, j - 2w, j - w。

所以對於 j % w 相同的狀態，其實可以用一個單調隊列來維護答案

接下來要來看如何維護單調隊列裡面每項的 value。假若 dp(i, j) 從 dp(i - 1, j - kw) 轉移，轉移式就是 dp(i, j) = dp(i - 1, j - kw) + k * v，那我們要怎麼樣在單調對列裡面表示這個 k * w 的貢獻呢 ? 我們使用了一個類似前綴和的方法 假設我們將 j - kw 表示成 w'，那麼轉移式就變成

dp(i, j)

• = dp(i - 1, j - kw) + k * v

• = dp(i - 1, w') + ((j - w') / w) * v

• = dp(i - 1, w') + (j / w) * v - (w' / w) * v

• = dp(i - 1, w') - (w' / w) * v + (j / w) * v

其中我們就可以把 dp(i - 1, w') - (w' / w) * v 做為單調對列裡面的值，最後出來再統一加上 (j / w) * v 即可。注意到電腦是直接取下高斯，不過 j % w 與 j - kw % w 會是一樣的，所以不會有問題。

​x
#include <bits/stdc++.h>
#define int long long
#define ALL(x) x.begin(),x.end()
using namespace std;

const int MAXN = 1e2 + 5;
const int MAXW = 1e5 + 5;
int n, m;
int w[MAXN], v[MAXN], c[MAXN];
int val[MAXN][MAXW], dp[MAXN][MAXW];

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> w[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    for (int i = 1; i <= n; i++) {
        for (int r = 0; r < w[i]; r++) {
            deque<int> dq;
            for (int j = r; j <= m; j += w[i]) {
                val[i][j] = dp[i - 1][j] - (j / w[i]) * v[i];
                while (!dq.empty() && val[i][dq.back()] <= val[i][j]) {
                    dq.pop_back();
                }
                dq.push_back(j);
                dp[i][j] = val[i][dq.front()] + (j / w[i]) * v[i];
                if (dq.front() == j - c[i] * w[i]) {
                    dq.pop_front();
                }
            }
        }
    }
    cout << dp[n][m] << '\n';
}